#include <iostream>
#include "BiGraph.h"
#include <fstream>
#include <limits>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;
using std::pair;


using namespace std;

void read_file(int& start, BiGraph<int>& BGraph)
{
	
	ifstream in("in.txt", ifstream::in);
	if (!in.is_open()) 
	{ 
		cout<<"File Error"<<endl;
		system("pause");
		exit(1);
	}
	int n;
	in>>n;
	in>>start;

	for (int i=0; i<n; i++)
	{
		for (int j=0; j<n; j++)
		{
			double weight;
			int v1, v2;
			in>>v1>>v2>>weight;
			BGraph.add_edge(v1, v2, weight);
			BGraph.add_edge(v2, v1, weight);

		}
	}
	in.close(); 
}

void relax(BiGraph<int>::Vertex* v, BiGraph<int>& BGraph, map<BiGraph<int>::Vertex*, double>& open, map<int, int>& parent)
		 {
			 pair<BiGraph<int>::out_edge_iterator, BiGraph<int>::out_edge_iterator> edges=v->out_edge();
			 for (BiGraph<int>::out_edge_iterator itr_e=edges.first; itr_e!=edges.second; itr_e++)
			 {
				 if (itr_e->get_weight()<numeric_limits<double>::max())
				 {
					 BiGraph<int>::Vertex* u=BGraph.find_or_create_vertex((itr_e->get_name()).second);
					 if (open.find(u)!=open.end() && open[u]>open[v]+(itr_e->get_weight()))
					 {
						 open[u]=open[v]+(itr_e->get_weight());
						 parent[u->get_name()]=v->get_name();
					 }
				 }
			 }
		 }

void dijkstra(BiGraph<int>& BGraph, int start)
		{
			BiGraph<int>::vertices_range vertices=BGraph.vertices();
			int n=BGraph.vertices_count();
			map<BiGraph<int>::Vertex*, double> open;
			map<int, int> parent;
			for (BiGraph<int>::vertex_iterator itr_v=vertices.first; itr_v!=vertices.second; itr_v++) 
			{
				open.insert(make_pair(BGraph.find_or_create_vertex(itr_v->get_name()), numeric_limits<double>::max()));
			}
			BiGraph<int>::Vertex* start_v=BGraph.find_or_create_vertex(start);
			open[start_v]=0;
			parent[start]=start;
			while (!open.empty())
			{
				BiGraph<int>::Vertex* v=(min_element(open.begin(), open.end()))->first;
				relax(v, BGraph, open, parent);
				open.erase(v);
			}

			for (BiGraph<int>::vertex_iterator itr_v=vertices.first; itr_v!=vertices.second; itr_v++) 
			{
				cout<<"Vertex "<<itr_v->get_name()<<endl;
				int vert=itr_v->get_name();
				vector<int> path;
				while (vert!=start)
				{
					path.push_back(vert);
					vert=parent[vert];
				}
				path.push_back(start);
				reverse(path.begin(), path.end());
				for(vector<int>::iterator itr=path.begin(); itr!=path.end(); itr++) 
				{
					cout << *(itr) << " ";
				}
				cout<<endl;

			}
		}

int main()
{
	BiGraph<int> BGr;
    int start;
	read_file(start, BGr);
	//BGr.show();
	dijkstra(BGr, start);
	system("pause");
	return 0;
}

